<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>封装双向链表</title>
</head>

<body>
    <script>
        //封装双向链表类
        function DoubleLinklist() {
            //封装内部类：节点类
            function Node(data) {
                this.data = data
                this.prev = null
                this.next = null
            }

            //属性
            this.head = null
            this.tail = null
            this.length = 0

            //append方法
            DoubleLinklist.prototype.append = data => {
                //1.根据data创建新节点
                let newNode = new Node(data)

                //2.添加节点
                //情况1：添加的是第一个节点
                if (this.length == 0) {
                    this.tail = newNode
                    this.head = newNode
                    //情况2：添加的不是第一个节点
                } else {
                    newNode.prev = this.tail
                    this.tail.next = newNode
                    this.tail = newNode
                }

                //3.length+1
                this.length += 1
            }


            // insert方法----插入节点
            DoubleLinklist.prototype.insert = function (position, data) {
                // 1. 越界判断
                if (position < 0 || position > this.length) return false

                //  2. 根据data创建新的节点
                var newNode = new Node(data)

                //  3. 插入新节点
                // 3.1 原链表为空的情况--插入的节点是第一个节点
                if (this.length === 0) {
                    this.head = newNode
                    this.tail = newNode
                    // 3.2 下面是原链表不为空的情况
                } else {
                    //  3.2.1 在第一个位置插入  position = 0
                    if (position === 0) {
                        this.head.prev = newNode
                        newNode.next = this.head
                        this.head = newNode
                        // 3.2.2 当插入的位置position === this.length时
                    } else if (position === this.length) {
                        this.tail.next = newNode
                        newNode.prev = this.tail
                        this.tail = newNode
                        //  3.2.3 当插入的位置 0 < position < this.length时
                    } else {
                        var current = this.head
                        var index = 0
                        while (index++ < position) {
                            current = current.next
                        }
                        // 交换节点信息--修改position位置前后节点信息变量的指向
                        newNode.next = current
                        newNode.prev = current.prev
                        current.prev.next = newNode
                        current.prev = newNode
                    }

                }

                // 4. 链表的长度加1
                this.length += 1
                return true   // 返回true表示插入成功



            }

            //  4.get(position)方法---当链表长度比较长时，采用从前往后遍历
            // 比如长度是100，我要找索引为98的元素，从头往后就比较麻烦
            // DoubleLinklist.prototype.get = function (position) {
            //     // 1.越界判断
            //     if (position < 0 || position >= this.length) return null
            //     // 2. 获取元素
            //     let current = this.head
            //     let index = 0
            //     while (index++ < position) {
            //         // 更新current位置
            //         current = current.next
            //     }
            //     return current.data
            // }

            // get(position)方法2----
            DoubleLinklist.prototype.get = function (position) {
                // 1. 越界判断
                if (position < 0 || position > this.length) return null
                // 2. 获取元素
                let current = this.head
                let index = 0
                // this.lenth / 2 > position  ---> 从头往后遍历
                if ((this.length / 2) > position) {
                    while (index++ < position) {
                        current = current.next
                    }  // 如果this.length / 2 < position ---->从后往前遍历
                } else {
                    current = this.tail
                    index = this.length - 1
                    while (index-- > position) {
                        current = current.prev
                    }
                }
                return current.data

            }

            // 5. 实现indexOf---查找对应的元素，返回索引的方法
            DoubleLinklist.prototype.indexOf = function (data) {
                // 1.定义变量
                let current = this.head
                let index = 0
                // 2.循环遍历列表-查找与data相同的节点
                while (current) {
                    if (current.data === data) {
                        return index
                    }
                    current = current.next
                    index += 1
                }
                // 如果在链表里找不到对应的值，就返回-1
                return -1
            }

            // 6. update 修改方法
            DoubleLinklist.prototype.update = function (position, newData) {
                // 1. 越界判断
                if (position < 0 || this.length <= position) return false
                // 2. 寻找正确的节点
                let current = this.head
                let index = 0
                while (index++ < position) {
                    // 更新current的指向
                    current = current.next
                }
                current.data = newData
                return true   // 代表修改成功
            }

            // 7. removeAt方法
            DoubleLinklist.prototype.removeAt = function (position) {
                // 1. 遇到position就进行越界判断
                if (position < 0 || position > this.length) return null

                //  2. 判断链表内是否只有一个节点
                let current = this.head   // 为了将所有数据能够返回--提升访问权限
                if (this.length == 1) {
                    this.header = null
                    this.tail = null
                } else {
                    // 2.1 < position < this.length --- 让要删除的节点没有别人指向它，它就会被浏览器自动回收
                    // 2.1要删除的是第一个节点
                    if (position == 0) {
                        // 将要删除节点的下一个节点，将其指向空
                        this.head.next.prev = null
                        // 将head指向要删除节点的下一个节点
                        this.head = this.head.next
                        // 2.2 要删除的是最后一个节点
                    } else if (position == this.length - 1) {
                        current = this.tail   // 删除的是最后一个节点
                        // 将要删除节点的前一个节点，将其指向空
                        this.tail.prev.next = null
                        // 将tail指向要删除节点的前一个节点
                        this.tail = this.tail.prev
                    } else {
                        //  3. 删除中间的节点--让其前一个和后一个节点取消对它的指向即可
                        let index = 0
                        while (index++ < position) {
                            // 遍历链表---更新current的指向
                            current = current.next
                        }
                        current.prev.next = current.next
                        current.next.prev = current.prev
                    }
                    // 4. length链表长度减1
                    this.length -= 1
                    return current.data  // 返回被删除结点后的数据
                }
            }

            // 8. remove方法
            DoubleLinklist.prototype.remove = function (data) {
                // 1.根据indexOf方法获得data的索引
                var index = this.indexOf(data)
                // 2. 根据返回的索引利用removeAt方法删除元素
                return this.removeAt(index)
            }

            // 9. isEmpty方法
            DoubleLinklist.prototype.isEmpty = function () {
                return this.length == 0
            }

            // 10.size方法
            DoubleLinklist.prototype.size = function () {
                return this.length
            }

            // 11 getHead 获取链表的第一个元素
            DoubleLinklist.prototype.getHead = function () {
                return this.head.data
            }

            // 12 getTail 获取链表的最后一个元素
            DoubleLinklist.prototype.getTail = function () {
                return this.tail.data
            }



        }

        //测试代码
        //1.创建双向链表
        let list = new DoubleLinklist()

        //2.测试append方法
        list.append('aaa')
        list.append('bbb')
        list.append('ccc')
        list.append('ddd')
        list.append('eee')
        list.append('fff')
        list.append('ggg')
        list.append('rrr')

        // console.log(list);
        // alert(list)

        //3.测试insert方法
        // list.insert(0, '插入链表的第一个元素')
        // list.insert(0, '在链表首部插入元素')
        // list.insert(1, '在链表中间插入元素')
        // list.insert(3, '在链表尾部插入元素')
        // console.log(list);
        // alert(list)

        // 4. 测试get方法
        // console.log(list.get(0))   // aaa
        // console.log(list.get(2))   // ccc
        // console.log(list.get(6))   // ggg

        // 5. indexOf方法
        // console.log(list.indexOf('eee'));   // 4
        // console.log(list.indexOf('aaa'));   // 0

        // 6. update方法
        // console.log(list.update(0, 'ppp'))  // true
        // console.log(list.update(2, 'vvv'))  // true
        // console.log(list)  // 两个位置的元素修改成功了


        // removeAt方法
        console.log(list.removeAt(0));  // aaa----返回要删除的元素
        console.log(list.removeAt(2))   // ddd
        console.log(list);

        // 8 remove方法
        console.log(list.remove('rrr'));  // rrr----返回要删除的元素
        console.log(list.remove('ccc'));  // ccc
        console.log(list)  // ---->删除成功了

        // 测试其他方法
        list.append('zzz')
        list.append('xxx')
        list.append('ccc')
        list.append('vvv')
        // isEmpty方法
        console.log(list.isEmpty())   // false

        // size方法
        console.log(list.size())      // 8

        // getHead方法
        console.log(list.getHead())   // bbb

        // getTail方法
        console.log(list.getTail())    // vvv

    </script>
</body>

</html>